#dfs
class Solution:
    def dfs(self, grid, r, c):
        grid[r][c] = 0
        nr, nc = len(grid), len(grid[0])
        for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
            if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
                self.dfs(grid, x, y)

    def numIslands(self, grid) -> int:
        nr = len(grid)
        if nr == 0:
            return 0
        nc = len(grid[0])
        num_islands = 0
        for r in range(nr):
            for c in range(nc):
                if grid[r][c] == "1":

                    num_islands += 1
                    self.dfs(grid, r, c)

        return num_islands
import collections

#bds
class Solution_():
    def numIslands(self,grid):
        nr=len(grid)
        if nr==0:
            return 0
        nc=len(grid[0])
        num_islands=0
        for r in range(nr):
            for c in range(nc):
                if grid[r][c]=='1':
                    num_islands+=1
                    grid[r][c]='0'
                    neighbors=collections.deque([(r,c)])
                    while neighbors:
                        row,col=neighbors.popleft()
                        for x,y in [(row-1,col),(row+1,col),(row,col-1),(row,col+1)]: #细节   （row-1,c）>>(row-1,col)
                            if 0<=x<nr and 0<=y<nc and grid[x][y]=='1':
                                neighbors.append((x,y))
                                grid[x][y]='0'
        return num_islands

class UnionFind():
    def __init__(self,grid):
        m,n=len(grid),len(grid[0])
        self.count=0
        self.parent=[-1]*(m*n)
        self.rank=[0]*(m*n)
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='1':
                    self.parent[i*n+j]=i*n+j
                    self.count+=1
    def find(self,i):
        if self.parent[i]!=i:
            self.parent[i]=self.find(self.parent[i])
        return self.parent[i]
    def union(self,x,y):
        rootx=self.find(x)
        rooty=self.find(y)
        if rootx!=rooty:
            if self.rank[rootx]<self.rank[rooty]:
                rootx,rooty=rooty,rootx
            self.parent[rooty]=rootx
            if self.rank[rootx]==self.rank[rooty]:
                self.rank[rootx]+=1
            self.count-=1
    def getCount(self):
        return self.count
class Solution__():
    def numIslands(self,grid):
        nr=len(grid)
        if nr==0:
            return 0
        nc=len(grid[0])
        unm_inlands=0
        uf=UnionFind(grid)
        for r in range(nr):
            for c in range(nc):
                if grid[r][c]=='1':
                    grid[r][c]='0'
                    for x,y in [(r-1,c),(r+1,c),(r,c-1),(r,c+1)]:
                        if 0<=x<nr and 0<=y<nc and grid[x][y]=='1':
                            uf.union(r*nc+c,x*nc+y)
        return uf.getCount()
s=Solution__()

arr=[['1','1'],['0','1']]

print(s.numIslands(arr))
